package experiment3.shudu001.models;

/**
 * Created by HP on 2025/4/26.
 */

public class SudokuSolver {
    private static final int SIZE = 9;
    private static final int EMPTY = 0;
    private int solutionCount = 0;
    public int[][] solve(int[][] board) {
        int[][] solution = copyBoard(board);
        if (solveSudoku(solution)) {
            return solution;
        }
        return null;
    }

    public int countSolutions(int[][] board) {
        solutionCount = 0;
        int[][] tempBoard = copyBoard(board);
        countSolutions(tempBoard, 0, 0);
        return solutionCount;
    }

    private boolean solveSudoku(int[][] board) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                if (board[row][col] == EMPTY) {
                    for (int number = 1; number <= 9; number++) {
                        if (isValid(board, row, col, number)) {
                            board[row][col] = number;

                            if (solveSudoku(board)) {
                                return true;
                            } else {
                                board[row][col] = EMPTY;
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private void countSolutions(int[][] board, int row, int col) {
        if (row == SIZE) {
            solutionCount++;
            return;
        }

        if (col == SIZE) {
            countSolutions(board, row + 1, 0);
            return;
        }

        if (board[row][col] != EMPTY) {
            countSolutions(board, row, col + 1);
            return;
        }

        for (int number = 1; number <= 9 && solutionCount < 2; number++) {
            if (isValid(board, row, col, number)) {
                board[row][col] = number;
                countSolutions(board, row, col + 1);
                board[row][col] = EMPTY;
            }
        }
    }

    private boolean isValid(int[][] board, int row, int col, int number) {
        // 检查行
        for (int c = 0; c < SIZE; c++) {
            if (board[row][c] == number) return false;
        }

        // 检查列
        for (int r = 0; r < SIZE; r++) {
            if (board[r][col] == number) return false;
        }

        // 检查3x3方块
        int boxRow = row / 3 * 3;
        int boxCol = col / 3 * 3;
        for (int r = boxRow; r < boxRow + 3; r++) {
            for (int c = boxCol; c < boxCol + 3; c++) {
                if (board[r][c] == number) return false;
            }
        }

        return true;
    }

    private int[][] copyBoard(int[][] board) {
        int[][] copy = new int[SIZE][SIZE];
        for (int row = 0; row < SIZE; row++) {
            System.arraycopy(board[row], 0, copy[row], 0, SIZE);
        }
        return copy;
    }

}
